package mt;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author zhangmin
 * @create 2022-03-26 17:39
 * 中位数
 */
class DualHeap{
    //small是一个大顶堆，存放较小的一半元素
    PriorityQueue<Integer> small=new PriorityQueue<>(((o1, o2) -> o2-o1));
    //large是一个小顶堆，存储较大的一半元素
    PriorityQueue<Integer> large=new PriorityQueue<>();

    //使用map记录延迟删除的元素，元素和需要被删除的次数
    private Map<Integer,Integer> delayed=new HashMap<>();
    private int k;//滑动窗口大小
    //记录大顶堆和小顶堆去除延迟删除元素后的大小
    private int smallSize=0,largeSize=0;

    public DualHeap(int k){
        this.k=k;
    }
    public void insert(Integer num) {
        if (small.isEmpty()||small.peek()>=num){
            //不需要进行处理，最后会调用balance
            small.offer(num);
            smallSize++;
        }else {
            large.offer(num);
            largeSize++;
        }
        makeBalance();
    }

    // 不断地弹出 heap 的堆顶元素，并且更新哈希表
    private void prune(PriorityQueue<Integer> heap) {
        while (!heap.isEmpty()){
            int num=heap.peek();
            if (delayed.containsKey(num)){
                //堆顶元素是需要被删除的
                delayed.put(num,delayed.get(num)-1);
                if (delayed.get(num)==0){
                    delayed.remove(num);
                }
                heap.poll();
            }else {
                break;
            }
        }
    }
    //调整两堆的大小，使得二者的元素个数满足要求
    private void makeBalance() {
        if (smallSize>largeSize+1){
            //small的数量比large多2个以上了。需要将small中的元素移动到large中
            large.offer(small.poll());
            smallSize--;
            largeSize++;
            //small顶元素被移除，需要进行small的prune
            prune(small);
        }else if (smallSize<largeSize){
            small.offer(large.poll());
            smallSize++;
            largeSize--;
            //large堆顶元素被移除，需要进行prune
            prune(large);
        }
    }
    public void delete(int n){
        if (!small.isEmpty()&&small.contains(n)){
            small.remove(n);
        }
        if (!large.isEmpty()&&large.contains(n)){
            large.remove(n);
        }
    }

    public double getMedian() {
        return (k&1)==1?small.peek():((double)small.peek()+large.peek())/2;
    }
}

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        int index=0;
        double[] res=new double[n-k+1];

        DualHeap m=new DualHeap(k);
        for (int i = 0; i < n; i++) {
            if (i<k){
                    m.insert(nums[i]);
                    if (i==k-1){
                        res[index++]=m.getMedian();
                    }
            }else {
                m.insert(nums[i]);
                m.delete(nums[i-k]);
                res[index++]=m.getMedian();
            }
        }
        return res;
    }
}
public class meituan_0326_4 {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int n=cin.nextInt();
        int[] nums=new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=cin.nextInt();
        }
    }
}
